#include <iostream>
#include <string>
#include <map>
#include <climits>
#include <vector>
#include <fstream>

#include "common.h"

using std::make_pair;

enum backtrackArrow {
  up,
  left,
  diagonal,
  start
};

std::string seqRNA("GGGGGGGGGCUUAGCGGG");
std::string seqDNA("AAAAAAAAACTTAGCAAA");
std::map<char,std::map<char,int> > matScore;
int penGapOpen = 1;
int penGapExt = 1;
int threshold = 5;
std::vector<exon> listExons;

std::map<int,std::map<int,std::pair<int,backtrackArrow> > > LocalAlignmentScoreTable;
std::map<int,std::map<int,int> > LocalAlignmentDownScoreTable;
std::map<int,std::map<int,int> > LocalAlignmentRightScoreTable;

int score(char x, char y) {
  if(matScore.count(x) && matScore[x].count(y)) return matScore[x][y];
  return -100;//INT_MIN;
}

std::pair<int,backtrackArrow> LocalAlignmentScore(int i, int j) {
  if(i < 0 || j < 0) return make_pair(0,start);
  if(LocalAlignmentScoreTable.count(i) && LocalAlignmentScoreTable[i].count(j)) {
    return LocalAlignmentScoreTable[i][j];
  }
  LocalAlignmentDownScoreTable[i][j] = std::max(LocalAlignmentDownScoreTable[i-1][j] - penGapExt, LocalAlignmentScore(i-1,j).first - penGapOpen - penGapExt);
  LocalAlignmentRightScoreTable[i][j] = std::max(LocalAlignmentRightScoreTable[i][j-1] - penGapExt, LocalAlignmentScore(i,j-1).first - penGapOpen - penGapExt);
  LocalAlignmentScoreTable[i][j] = make_pair(std::max(std::max(0,LocalAlignmentDownScoreTable[i][j]),std::max(LocalAlignmentRightScoreTable[i][j],LocalAlignmentScore(i-1,j-1).first+score(seqRNA[i],seqDNA[j]))),start);
 
  if(LocalAlignmentScoreTable[i][j].first == 0) { 
    ;
  }
  else if(LocalAlignmentScoreTable[i][j].first == LocalAlignmentDownScoreTable[i][j]) {
    LocalAlignmentScoreTable[i][j] = make_pair(LocalAlignmentScoreTable[i][j].first,up);
  }
  else if(LocalAlignmentScoreTable[i][j].first == LocalAlignmentRightScoreTable[i][j]) {
    LocalAlignmentScoreTable[i][j] = make_pair(LocalAlignmentScoreTable[i][j].first,left);
  }
  else LocalAlignmentScoreTable[i][j] = make_pair(LocalAlignmentScoreTable[i][j].first,diagonal);
  return LocalAlignmentScoreTable[i][j];
}

int main(int argc, char * argv[]) {
  std::fstream DNA;
  DNA.open("data/yap1-human.txt");
  seqDNA = "";
  DNA >> seqDNA;
  
  std::fstream RNA;
  RNA.open("data/yap1-mRNA-mouse-9.txt");
  seqRNA = "";
  RNA >> seqRNA;

  matScore['A']['A'] = 1;
  matScore['G']['G'] = 1;
  matScore['C']['C'] = 1;
  matScore['U']['T'] = 1;
  matScore['T']['U'] = 1;
  matScore['T']['T'] = 1;
  for(int i = 0; i < (int)seqRNA.size(); i++) { 
    for(int j = 0; j < (int)seqDNA.size(); j++) { 
      if(LocalAlignmentScore(i,j).first >= threshold) {
	int bi = i;
	int bj = j;
	std::string exon;
	std::string oppositeExon;
	while(LocalAlignmentScore(bi,bj).second != start) {
	  if(LocalAlignmentScore(bi,bj).second == diagonal) { 
	    exon = seqDNA[bj] + exon; 
	    oppositeExon = seqRNA[bi] + oppositeExon;
	    bj--; 
	    bi--; 
	  }
	  if(LocalAlignmentScore(bi,bj).second == left) { exon = seqDNA[bj] + exon; oppositeExon = '-' + oppositeExon; bj--; }
	  if(LocalAlignmentScore(bi,bj).second == up) { exon = '-' + exon; oppositeExon = seqRNA[bi] + oppositeExon; bi--; }
	}
	::exon result;
	result.l = bj+1;
	result.r = j;
	result.w = LocalAlignmentScore(i,j).first;
	listExons.push_back(result);
      }
    }
  }
  for(size_t i = 0; i < listExons.size(); i++) {
    std::cout << "Putative Exon: " << listExons[i].l  << "-" << listExons[i].r << " (" << listExons[i].w << ") " << seqDNA.substr(listExons[i].l,listExons[i].r - listExons[i].l + 1) << std::endl;
  }  
  return 0;
}
